package lib

//link to 08.14
func init() {
	Probs = append(Probs, Problem{
		Num:         241,
		Discription: "给运算表达式添加括号，返回所有结果",
		Level:       2,
		Labels: map[string]int{
			"回溯": 1,
			"分治": 1,
			"记忆化搜索": 1,
		},
	})
}

func DiffWaysToCompute(expression string) []int {
	//先把表达式转化为数组，+用-1表示，-用-2表示，*用-3表示
	exp := make([]int, 0)
	tempNum := 0
	for i := range expression {
		ch := expression[i]
		if ch >= '0' && ch <= '9' {
			tempNum = tempNum*10 + int(ch-'0')
		} else {
			exp = append(exp, tempNum)
			tempNum = 0
			switch ch {
			case '+':
				exp = append(exp, -1)
			case '-':
				exp = append(exp, -2)
			case '*':
				exp = append(exp, -3)
			}
		}
	}
	exp = append(exp, tempNum)

	cal := func(x, y, op int) int {
		switch op {
		case -1:
			return x + y
		case -2:
			return x - y
		case -3:
			return x * y
		}

		return 0
	}

	n := len(exp)
	//记忆化搜索
	expMap := make(map[[2]int][]int, 0)
	var dfs func(int, int) []int
	//求exp[i:j+1]表达式结果的所有可能值
	dfs = func(start, end int) []int {
		if start == end {
			return []int{exp[start]}
		}

		if vals, exist := expMap[[2]int{start, end}]; exist {
			return vals
		}

		res := make([]int, 0)
		//遍历所有可能的符号位置
		for i := start + 1; i <= end-1; i += 2 {
			//遍历左右表达式可能的值
			leftNums := dfs(start, i-1)
			rightNums := dfs(i+1, end)
			for _, leftVal := range leftNums {
				for _, rightVal := range rightNums {
					res = append(res, cal(leftVal, rightVal, exp[i]))
				}
			}
		}

		expMap[[2]int{start, end}] = res
		return res
	}

	return dfs(0, n-1)
}